/**
 * 归并排序算法
 * @param {*} arr 数组
 * @returns 有序数组
 */
function mergeSort(arr) {
  // 采用自上而下的递归方法
  const N = arr.length;
  if (N < 2) {
    // 递归出口，数组只有一个元素，直接返回这个数组
    return arr;
  }
  // x >> 1 是位运算中的右移运算，表示右移一位，等同于 x 除以 2 再取整，即 x >> 1 === Math.floor(x / 2)
  // N >> 1 和 Math.floor(N / 2) 等价
  let middle = N >> 1;
  // 拆分为两个子数组
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  // 递归调用mergeSort
  return merge(mergeSort(left), mergeSort(right));
}


/**
 * 对两个有序数组进行合并操作
 * @param {*} left left数组
 * @param {*} right right数组
 * @returns 一个有序数组temp
 */
function merge(left, right) {
  // 临时数组存储归并后的数据
  const temp = [];
  // 两个数组都还没有遍历结束
  while (left.length && right.length) {
    // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
    if (left[0] <= right[0]) {
      // left[0]小，删除left数组中第一项left[0]，并将它放入temp数组中
      temp.push(left.shift());
    } else {
      // 删除right数组中第一项，并将它放入temp数组中
      temp.push(right.shift());
    }
  }
  // left数组还有元素，right数组遍历完了
  while (left.length) {
    // 将left数组剩下的元素都放入temp数组中
    temp.push(left.shift());
  }
  // right数组还有元素，left数组遍历完了
  while (right.length) {
    temp.push(right.shift());
  }
  // 返回排序好的数组
  return temp;
}
